
class Solution {
    //方法1
    public int[] countBits(int num) {
        int[] a = new int[num+1];
        for(int i=0;i<=num;i++){
            a[i] = a[i >> 1] + (i&1);
        }
        return a;
    }
    //方法2
    public int[] countBits(int num) {
        int[] a = new int[num+1];
        a[0] = 0;
        int b =1;
        for(int i=1;i<num+1;i++){
            int x = i -b;
            while(x >= b){
                b = b << 1;
                x = i - b;
            }
            a[i] = a[x] + 1;
        }
        return a;
    }
}